//
// Created by Administrator on 2021/9/8.
//

//假设 力扣（LeetCode）即将开始 IPO 。为了以更高的价格将股票卖给风险投资公司，
// 力扣 希望在 IPO 之前开展一些项目以增加其资本。 由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。
// 帮助 力扣 设计完成最多 k 个不同项目后得到最大总资本的方式。
//
//给你 n 个项目。对于每个项目 i ，它都有一个纯利润 profits[i] ，和启动该项目需要的最小资本 capital[i] 。
//
//最初，你的资本为 w 。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。
//
//总而言之，从给定项目中选择 最多 k 个不同项目的列表，以 最大化最终资本 ，并输出最终可获得的最多资本。
//
//答案保证在 32 位有符号整数范围内。
//
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/ipo
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。


#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <climits>
#include <stack>

using namespace std;

class Solution {
public:
    /**
     * 选择利润最大的几样项目进行——大根堆
     * 能选择项目的前提：当前的资金大于其启动资金
     * @param k
     * @param w
     * @param profits
     * @param capital
     * @return
     */
    int findMaximizedCapital(int k, int w, vector<int> &profits, vector<int> &capital) {
        int n = static_cast<int>(profits.size());
        vector<pair<int, int>> v;
        v.reserve(n);
        for (int i = 0; i < n; ++i) {
            v.emplace_back(profits[i], i);
        }
        // 排序 从大到小
        sort(v.rbegin(), v.rend());
        unordered_set<int> used;
        for (int i = 0; i < k; ++i) {
            // 每次都找利润最大 且当前启动资金足够  且没进行过的
            int j = 0;
            for (; j < n; ++j) {
                if (capital[v[j].second] <= w and !used.count(v[j].second))
                    break;
            }
            if (j == n)
                return w;
            used.insert(v[j].second);
            w += profits[v[j].second];
        }
        return w;
        // 超时  32/35
    }

    int findMaximizedCapital2(int k, int w, vector<int> &profits, vector<int> &capital) {
        // 首先挑出当前资金下可以进行的项目，放进优先队列中
        // 完成一个项目后，更新资金，再将更多的项目放入可执行队列
        int n = (int) profits.size();
        int curr = 0;  // 指针 指向当前可以进行的项目
        priority_queue<int> pq;  // 可执行项目利润的优先队列
        vector<pair<int, int>> arr;  // 所有项目的排序数组
        arr.reserve(n);
        for (int i = 0; i < n; ++i) {
            arr.emplace_back(capital[i], profits[i]);
        }
        sort(arr.begin(), arr.end()); // 按照需要的资金进行排序
        for (int i = 0; i < k; ++i) {
            // 将启动资金小于当前资金的项目放入可执行队列
            while (curr < n and arr[curr].first <= w) {
                pq.push(arr[curr].second);  // 存利润
                ++ curr;
            }
            if (!pq.empty()) {
                w += pq.top(); // 完成项目，增加资金
                pq.pop();
            } else {
                break;
            }
        }
        return w;
    }
};

int main() {
    vector<int> profits{1, 2, 3};
    vector<int> capital{0, 1, 1};
    Solution solution;
    cout << solution.findMaximizedCapital(2, 0, profits, capital) << endl;
    return 0;
}
